<!DOCTYPE html>
<html lang="en">
<head>
  <meta charset="UTF-8">
  <title>Title</title>
</head>
<body>
单端队列
后进后出，从后进从前出
基本方法有：
1. 入队
2. 出队
3. 队列长度
4. 队头
5. 清空
6. 是否为空
<script>
	{
		class Queue {
			#items = {}
      #front = 0
      #last = 0

      // 入队
      enqueue (val) {
				this.#items[this.#last++] = val
      }
			// 出队
      dequeue () {
				if (this.isEmpty()) return
        const val = this.#items[this.#front]
        delete this.#items[this.#front]
	      this.#front ++
        return val
      }
      // 队列长度
      size () {
				return this.#last - this.#front
      }
      // 队头
      front () {
				return this.#items[this.#front]
      }
      // 清空
      clear () {
				this.#items = {}
        this.#front = 0
        this.#last = 0
      }
      // 是否为空
      isEmpty () {
				return this.size() === 0
      }
    }
  }
</script>

双端队列
队列两头都可以入队和出队
基本方法有：
1. 从前入队
2. 从前出队
3. 从后入队
4. 从后出队
5. 对头
6. 队尾
7. 队长
8. 是否为空
9. 清空
<script>
	{
		class DoubleQueue {
			#items = {}
      #front = 0
      #last = 0

			// 从前入队
      frontEnqueue (val) {
				if (this.#front > 0) {
					this.#front --
          this.#items[this.#front] = val
        } else {
					for (let i = this.#last; i > 0; i --) {
						this.#items[i] = this.#items[i - 1]
          }
					this.#items[this.#front] = val
					this.#last ++
        }
      }
			// 从前出队
      frontDequeue () {
				if (this.isEmpty()) return
        const val = this.#items[this.#front]
        delete this.#items[this.#front]
	      this.#front ++
        return val
      }
			// 从后入队
      lastEnqueue (val) {
				this.#items[this.#last ++] = val
      }
			// 从后出队
      lastDequeue () {
				if (this.isEmpty()) return
        const val = this.#items[this.#last - 1]
        delete this.#items[this.#last - 1]
	      this.#last --
        return val
      }
			// 对头
      front () {
				return this.#items[this.#front]
      }
			// 队尾
			tail () {
				return this.#items[this.#last - 1]
			}
			// 队长
      size () {
				return this.#last - this.#front
      }
			// 是否为空
      isEmpty () {
				return this.size() === 0
      }
			// 清空
      clear () {
				this.#items = {}
        this.#front = 0
        this.#last = 0
      }
    }
  }
</script>





<script>
  class Queue {
    #items = {} // 如果用数组模拟队列的话，当从对头删除一个元素时，后面所有的元素都要向前移动一位，损耗性能
    #frontCount = 0
    #lastCount = 0

    enqueue (val) {
      this.#items[this.#lastCount] = val
      this.#lastCount ++
    }

    dequeue () {
      if (this.isEmpty()) return

      const val = this.#items[this.#frontCount]
      delete this.#items[this.#frontCount]
      this.#frontCount ++
      return val
    }

    front () {
      return this.#items[this.#frontCount]
    }

    isEmpty () {
      return this.size() === 0
    }

    clear () {
      this.#items = {}
      this.#frontCount = 0
      this.#lastCount = 0
    }

    size () {
      return this.#lastCount - this.#frontCount
    }

    toString () {
      if (this.isEmpty()) return ''

      let str = ''
      for (let i in this.#items) {
        str += `${this.#items[i]} `
      }

      return str
    }
  }

  const queue = new Queue()


  /*
  * 击鼓传花
  * */
  function getLuck (arr) {
    const queue = new Queue()
    for (const item of arr) {
      queue.enqueue(item)
    }

    return function (num) {
      if (num <= 0 || queue.size() <= 1) return

      while (queue.size() > 1) {
        for (let i = 1; i <= num; i ++) {
          queue.enqueue(queue.dequeue())
        }

        queue.dequeue()
      }

      return queue.front()
    }
  }

  const getLuckPerson = getLuck(['tom', 'jerry', 'joanna', 'tony', 'sara'])
  console.log(getLuckPerson(2))

  // 双端队列
  class DeQueue {
    #items = {}
    #frontCount = 0
    #lastCount = 0

    frontEnqueue (val) {
      // this.#frontCount --
      // this.#items[this.#frontCount] = val
      if (this.#frontCount > 0) {
        this.#frontCount --
        this.#items[this.#frontCount] = val
      } else {
        for (let i = this.#lastCount; i > 0; i --) {
          this.#items[i] = this.#items[i - 1]
        }
        this.#items[0] = val
        this.#lastCount ++
      }
    }

    frontDequeue () {
      if (this.isEmpty()) return

      const val = this.#items[this.#frontCount]
      delete this.#items[this.#frontCount]
      this.#frontCount ++

      return val
    }

    lastEnqueue (val) {
      this.#items[this.#lastCount] = val
      this.#lastCount ++
    }

    lastDequeue () {
      if (this.isEmpty()) return
      const val = this.#items[this.#lastCount - 1]
      delete this.#items[this.#lastCount - 1]
      this.#lastCount --
      return val
    }

    front () {
      return this.#items[this.#frontCount]
    }

    last () {
      return this.#items[this.#lastCount - 1]
    }

    isEmpty () {
      return this.size() === 0
    }

    clear () {
      this.#items = {}
      this.#frontCount = 0
      this.#lastCount = 0
    }

    size () {
      return this.#lastCount - this.#frontCount
    }

    toString () {
      if (this.isEmpty()) return ''

      let str = ''
      for (let i in this.#items) {
        str += `${this.#items[i]} `
      }

      return str
    }
  }

  const dequeue = new DeQueue()
</script>
</body>
</html>
